// easy

// 给定一个二叉树的根节点root和一个值targetSum
// 要求：判断该树中是否存在从根节点到叶子节点的路径，使得这条路径上所有节点值相加等于targetSum，如果存在，返回true，否则返回false

// 解题思路：递归遍历
// 1. 定义一个递归函数，传入当前根节点root，目标节点和targetSum，以及新增变量currSum（表示为从根节点到当前节点的路径上所有节点值之和）
// 2. 递归遍历左右子树，同时更新维护currSum值
// 3. 如果当前节点为叶子节点时，判断currSum是否与targetSum相等
//    如果currSum === targetSum,返回true
//    如果currSum !== targetSum, 返回false
// 4. 如果当前节点不为叶子节点，则继续递归遍历左右子树

// 时间复杂度：O(n)，n为二叉树的节点数目
// 空间复杂度：O(n)，递归函数需要用到栈空间，栈空间取决于递归深度，最坏情况下递归深度为n
function hasPathSum(root, targetSum) {
    function sum(root, targetSum, curSum) {
        if (!root) {
            return false
        }
        curSum += root.val
        if (!root.left && !root.right) {
            return curSum === targetSum
        } else {
            return sum(root.left, targetSum, curSum) || sum(root.right, targetSum, curSum)
        }
    }
    return sum(root, targetSum, 0)
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: {
            val: 3,
            left: {
                val: 4,
                left: null,
                right: null
            },
            right: null
        },
    },
    right: {
        val: 2,
        left: {
            val: 3,
            left: null,
            right: {
                val: 6,
                left: null,
                right: null
            }
        },
        right: null
    },
};

console.log(hasPathSum(root, 10));

function hasPathSum(root, target) {
    if (!root) {
        return false
    }
    if (!root.left && !root.right) {
        return target - root.val === 0
    }
    return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val)
}